Spastic paraplegia 7 is an autosomal recessive disorder caused by mutations in the gene encoding paraplegin, a protein located at the inner mitochondrial membrane and involved in the processing of other mitochondrial proteins. The mechanism whereby paraplegin mutations cause disease is unknown. We studied two female and two male adult patients from two Norwegian families with a combination of progressive external ophthalmoplegia and spastic paraplegia. Sequencing of SPG7 revealed a novel missense mutation, c.2102A>C, p.H 701P, which was homozygous in one family and compound heterozygous in trans with a known pathogenic mutation c.1454_1462del in the other. Muscle was examined from an additional, unrelated adult female patient with a similar phenotype caused by a homozygous c.1047insC mutation in SPG7. Immunohistochemical studies in skeletal muscle showed mosaic deficiency predominantly affecting respiratory complex I, but also complexes III and IV. Molecular studies in single, microdissected fibres showed multiple mitochondrial DNA deletions segregating at high levels (38–97%) in respiratory deficient fibres. Our findings demonstrate for the first time that paraplegin mutations cause accumulation of mitochondrial DNA damage and multiple respiratory chain deficiencies. While paraplegin is not known to be directly associated with the mitochondrial nucleoid, it is known to process other mitochondrial proteins and it is possible therefore that paraplegin mutations lead to mitochondrial DNA deletions by impairing proteins involved in the homeostasis of the mitochondrial genome. These studies increase our understanding of the molecular pathogenesis of SPG7 mutations and suggest that SPG7 testing should be included in the diagnostic workup of autosomal recessive, progressive external ophthalmoplegia, especially if spasticity is present.